package Data_Structure.MapAndSet;

import Data_Structure.MapAndSet.model.HashNode;
import com.sun.org.apache.xpath.internal.operations.Neg;


import java.util.HashMap;

/**
 * @className: MyHashMap
 * @author: 芃
 * @description: 模拟HashMap的底层原理-》HashBuck 哈希桶
 * @date: 2023/8/24 19:43
 */
public class MyHashBuck {
    public HashNode[] array;
    public int usedSize;//有效数据个数

    private final float DEFAULT_LOAD_FACTOR = 0.75f;//负载因子

    public MyHashBuck() {
        this.array = new HashNode[10];
    }

    //存放元素
    public void put(int key,int val){
        //①、找到Key所在的位置
        int index = getIndex(key);
        //②、遍历这个下标的链表，看是否有相同的Key，如果有，则更新value值
        HashNode cur = array[index];
        while (cur != null){
            if (cur.key == key){
                cur.value = val;//更新val值
                return;
            }
            cur = cur.next;
        }
        //③、走到这，说明该下标下的链表没有这个key，则把这个key放到头位置
        HashNode node = new HashNode(key,val);
        cur = array[index];
        array[index] = node;
        node.next = cur;
        this.usedSize++;
        //④、插入完成后，计算是否超过负载因子
        if (loadFactor() >= this.DEFAULT_LOAD_FACTOR){
            //扩容，重新哈希
            resize();
        }
    }
    //取元素
    public int get(int key){
        int index = getIndex(key);
        HashNode head = array[index];
        while (head != null){
            if (head.key == key){
                return head.value;
            }
            head = head.next;
        }
        return -1;
    }
    //根据key计算数组下标位置
    public int getIndex(int key){
        return key % this.array.length;
    }

    //计算负载因子
    private double loadFactor(){
        return (double) this.usedSize /array.length;
    }
    //扩容->二倍扩容，重新哈希
    private void resize(){
        HashNode[] newArr = new HashNode[array.length * 2];
        for (int i = 0; i < array.length; i++) {
            HashNode cur = array[i];
            while (cur != null){
                int index = cur.key % newArr.length;//计算新的下标
                HashNode curNext = cur.next;
                cur.next = newArr[index];
                newArr[index] = cur;
                cur = curNext;
            }
        }
        this.array = newArr;
    }
}
